home *** CD-ROM | disk | FTP | other *** search
/ ADA Programming Guide / ADA Programming Guide.iso / ada_a9x / cqsort.ada < prev    next >
Encoding:
Text File  |  1996-01-30  |  3.0 KB  |  120 lines
  1. WITH Ada.Text_IO, My_Int_IO; USE Ada.Text_IO, My_Int_IO;
  2.  
  3. PROCEDURE QSort IS -- 26-12-93
  4.     TYPE Data_Type IS ARRAY(Integer RANGE <>) OF Integer;
  5.     Data : Data_Type(1..20) := (10, 9, 8, 7, 6, 5, 4, 3, 2, 1  
  6.                                , 0,-1,-2,-3,-4,-5,-6,-7,-8,-9);
  7.  
  8.     PROCEDURE Swap(X, Y : IN OUT Integer) IS
  9.         Temp : Integer;
  10.     BEGIN
  11.         Temp := X;
  12.         X := Y;
  13.         Y := Temp;
  14.     END Swap;
  15.     
  16.     PROCEDURE Find_Pivot(Left : Integer; Right : Integer; Pivot : OUT Integer) IS
  17.  
  18.         FirstKey  : Integer := Data(Left);
  19.  
  20.     BEGIN
  21.         Pivot := 0;
  22.         FOR Up IN Left+1 .. Right LOOP
  23.             IF Data(Up) > FirstKey THEN
  24.                 Pivot := Up;
  25.                 EXIT;
  26.             ELSIF Data(Up) < FirstKey THEN
  27.                 Pivot := Left;
  28.                 EXIT;
  29.             END IF;
  30.         END LOOP;
  31.             
  32.     END Find_Pivot;
  33.  
  34.     PROCEDURE Partition(Left, Right : Integer;
  35.                         Pivot : Integer; 
  36.                         Partition_Point : OUT Integer) IS
  37.                             
  38.     Up   : Integer := Left;
  39.     Down : Integer := Right;
  40.     BEGIN
  41.         LOOP            
  42.             Swap(Data(Up),Data(Down));
  43.             WHILE Data(Up) < Pivot LOOP
  44.                 Up := Up + 1;
  45.             END LOOP;
  46.                 
  47.             WHILE Pivot <= Data(Down) LOOP
  48.                 Down := Down - 1;
  49.             END LOOP;
  50.                 
  51.             EXIT WHEN Up > Down;
  52.                 
  53.         END LOOP;
  54.             
  55.         Partition_Point := Up;
  56.             
  57.     END Partition;
  58.  
  59.     PROCEDURE CQuick_Sort(Left, Right : Integer) IS
  60.  
  61.         Pivot_Point     : Integer;
  62.         Pivot           : Integer;
  63.         Partition_Point : Integer;
  64.        
  65.     BEGIN
  66.  
  67.         Find_Pivot(Left,Right,Pivot_Point);
  68.  
  69.         IF Pivot_Point /= 0 THEN
  70.  
  71.             Pivot := Data(Pivot_Point);
  72.             Partition(Left,Right,Pivot,Partition_Point);
  73.  
  74.             DECLARE  
  75.  
  76.                 TASK TYPE CQSort IS
  77.                     ENTRY Start(First, Last : Integer);
  78.                 END;
  79.         
  80.         CQSort_Left, CQSort_Right : CQSort;
  81.  
  82.                 TASK BODY CQSort IS
  83.                     First_B, Last_B : Integer;    
  84.                 BEGIN
  85.         
  86.                     ACCEPT Start(First, Last : Integer) DO
  87.                         First_B := First;
  88.                         Last_B  := Last;
  89.                     END Start;
  90.                     IF First_B < Last_B THEN
  91.                         CQuick_Sort(First_B , Last_B);
  92.                 END IF;
  93.                 END;
  94.  
  95.             BEGIN
  96.             
  97.                 CQSort_Right.Start(Partition_Point,Right);
  98.                 CQSort_Left .Start(Left,Partition_Point - 1);
  99.                 
  100.             END;
  101.         END IF;
  102.  
  103.     END CQuick_Sort;
  104.         
  105. BEGIN
  106.  
  107.     FOR I IN Data'RANGE LOOP        
  108.         Put(Data(I),3);
  109.     END LOOP;
  110.  
  111.     New_Line;
  112.  
  113.     CQuick_Sort(Data'First , Data'Last);
  114.  
  115.     FOR I IN Data'RANGE LOOP        
  116.         Put(Data(I),3);
  117.     END LOOP;
  118.  
  119.     New_Line;
  120. END QSort;